package pro.softzhang.algo.lc800;

import pro.softzhang.algo.flag.book.BLeetCode75;
import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.knowledge.KBinarySearch;
import pro.softzhang.algo.flag.x.XClassic;

/**
 * 又是二分查找变形
 */
@BLeetCode75
@DRed
@KBinarySearch
@XClassic
public class LC875_KokoEatingBananas {
    public static void main(String[] args) {
        int[] piles = {3,6,7,11};
        int h = 8;
        int speed = new Solution().minEatingSpeed(piles, h);
        System.out.println(speed);
    }

    static
    class Solution {
        public int minEatingSpeed(int[] piles, int h) {
            int max = -1;
            for (int pile : piles) {
                max = Math.max(max, pile);
            }

            int left = 1, right = max;
            while (left <= right) {
                int middle = left + (right - left) / 2;
                int hours = calcHours(piles, middle);
                if(hours <= h) {
                    if(middle == 1 || calcHours(piles, middle - 1) > h) {
                        return middle;
                    }
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }

            return -1;
        }

        private int calcHours(int[] piles, int speed) {
            int hours = 0;
            for (int pile : piles) {
                hours += (pile + speed - 1) / speed;
            }
            return hours;
        }
    }
}